package mine.code.question.动态规划;

import org.junit.Test;

import java.util.Arrays;

/**
 * 给你一个整数数组 nums 和一个整数 target 。
 * <p>
 * 向数组中的每个整数前添加'+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
 * <p>
 * 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
 * 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [1,1,1,1,1], target = 3
 * 输出：5
 * 解释：一共有 5 种方法让最终目标和为 3 。
 *
 * @author caijinnan
 */
public class 目标和 {


    @Test
    public void run() {
//        [0,0,0,0,0,0,0,0,1]
//        1
        int[] nums = {0, 0, 0, 0, 0, 0, 0, 0, 1};
        int target = 1;
        System.out.println(findTargetSumWays(nums, target));
    }

    public int findTargetSumWays(int[] nums, int target) {
        int length = nums.length;
        if (length == 1) {
            int addNum = 0;
            if (nums[0]==target) {
                addNum++;
            }
            if(nums[0]==-target){
                addNum++;
            }
            return addNum;
        }
        int[] newNums = Arrays.copyOf(nums, nums.length - 1);
        return findTargetSumWays(newNums, target - nums[length - 1]) + findTargetSumWays(newNums, target + nums[length - 1]);
    }
}
